﻿// 0929train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>

using namespace std;


/*
 一个有N个选手参加比赛，选手编号为1~N（3<=N<=100）
 有M（3<=M<=10）个评委对选手进行打分。
打分规则为每个评委对选手打分，最高分10分，最低分1分
请计算得分最多的3位选手的编号
如果得分相同，则得分高分值最多的选手排名靠前
(10分数量相同，则比较9分的数量，以此类推，用例中不会出现多个选手得分完全相同的情况)

输入描述
第一行为半角逗号分割的两个正整数
第一个数字表示M（3<=M<=10）个评委，
第二个数字表示N（3<=N<=100）个选手
第2到M+1行是半角逗号分割的整数序列，表示评委为每个选手的打分，
0号下标数字表示1号选手分数，1号下标数字表示2号选手分数，依次类推

输出描述
选手前3名的编号。
注：若输入为异常，输出-1，如M、N、打分不在范围内

输入
4,5
10,6,9,7,6
9,10,6,7,5
8,10,6,5,10
9,10,8,4,9
输出
2,1,5
第一行代表有4个评委，5个选手参加比赛
矩阵代表是4*5，每个数字是选手的编号，每一行代表一个评委对选手的打分排序，
2号选手得分36分排第1，1号选手36分排第2，5号选手30分
（2号10分值有3个，1号10分值只有1个，所以2号排第一）
 */
class Solution01
{
public:
    static bool compare(pair<int, vector<int>>&p_1, pair<int, vector<int>>&p_2)
    {
        int sum_1 = 0, sum_2 = 0;
        unordered_map<int, int>map_1,map_2;
        for (auto&num:p_1.second)
        {
            sum_1 += num;
            map_1[num] += 1;
        }
        for (auto& num : p_2.second)
        {
            sum_2 += num;
            map_2[num] += 1;
        }

        vector<int>score_1, score_2;
        if (sum_1==sum_2)
        {
            for (auto&map_item: map_1)
            {
                score_1.push_back(map_item.first);
            }
            sort(score_1.rbegin(), score_1.rend());
            for (auto& map_item : map_2)
            {
                score_2.push_back(map_item.first);
            }
            sort(score_2.rbegin(), score_2.rend());

            
            int v_size = min(score_1.size(), score_2.size());
            for (int i=0; i<v_size;i++)
            {
                if (score_1[i] > score_2[i]) return true;
                if (score_1[i] < score_2[i]) return false;
                if (score_1[i]==score_2[i])
                {
                    int curr_score = score_1[i];
                    if (map_1[curr_score] > map_2[curr_score]) return true;
                    if (map_1[curr_score] < map_2[curr_score]) return false;
                }
            }
            return false;
        }
        return sum_1 > sum_2; //if(sum_1>sum_2)return true
	    //compare
    }

    Solution01(vector<vector<int>>&grid, int row_size, int col_size)
    {
        if (grid.empty()) return;
        //如果得分相同，则得分高分值最多的选手排名靠前
        unordered_map<int, vector<int>>score_map;

        for (int layer=0; layer<row_size; layer++)
        {
            vector<int>layer_v = grid[layer];
            for (int c=0; c<col_size; c++)
            {
                //最高分10分，最低分1分
                bool is_score = layer_v[c] >= 1 && layer_v[c] <= 10;
                if (!is_score)
                {
                    cout << -1;
                    return;
                }

            	//选手编号为1~N
                score_map[c + 1].push_back(layer_v[c]);
            }
        }

        //pair第一个score，第二个count
        //pair<int,vector<int>>
        vector<pair<int, vector<int>>>sort_vec;

        for (auto&map_item: score_map)
        {
            pair<int, vector<int>>item = make_pair(map_item.first, map_item.second);
            sort_vec.push_back(item);
        }

        sort(sort_vec.begin(), sort_vec.end(), compare);

        //选手前3名的编号
        vector<int>result;
        for (int i=0; i<3; i++)
        {
            result.push_back(sort_vec[i].first);
        }

        int result_size = result.size();
        for (int i=0; i< result_size; i++)
        {
            cout << result[i];
	        if (i!=result_size-1)
	        {
                cout << ',';
	        }
        }
	    //Solution01
    }
};

/*
 现需要将矩阵中所有的 1 进行反转为 0，规则如下： 
1. 当点击一个 1 时，该 1 被反转为 0，同时相邻的上、下、左、右，
以及左上、左下、右上、右下 8 个方向的 1 （如果存在 1）均会自动反转为 0

2. 进一步地，一个位置上的 1 被反转为 0 时，
与其相邻的 8 个方向的 1 （如果存在 1）均会自动反转为 0
按照上述规则示例中的矩阵只最少需要点击 2 次后，所有均值 0 

请问，给定一个矩阵，最少需要点击几次后，所有数字均为 0？

输入描述
第一行输入两个整数，分别表示矩阵的行数 N 和列数 M，取值范围均为 [1,100] 
接下来 N 行表示矩阵的初始值，每行均为 M 个数，取值范围 [0,1]

输出描述
输出一个整数，表示最少需要点击的次数

输入
3 3
1 0 1
0 1 0
1 0 1
输出
1
 */
class Solution02
{
public:
    void bfs(vector<vector<int>>& grid, 
        vector<vector<bool>>&checked,
        deque<vector<int>>&bfs_queue
    )
    {
        while (!bfs_queue.empty())
        {
            vector<int>top_node = bfs_queue.front();
            bfs_queue.pop_front();

            for (auto&dir_v:DirectionGrid)
            {
                int curr_r = top_node[0] + dir_v[0];
                int curr_c = top_node[1] + dir_v[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size_;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size_;

                if (!is_curr_r || !is_curr_c) continue;

                bool is_visited = checked[curr_r][curr_c];
                bool is_available = grid[curr_r][curr_c] == 1;

                if (!is_visited && is_available)
                {
                    bfs_queue.push_back({ curr_r,curr_c });
                    //标为已访问
                    checked[curr_r][curr_c] = true;
                }
                //for
            }


            //while
        }


        //bfs
    }
    Solution02(vector<vector<int>>&grid,int row_size, int col_size)
    {
        row_size_ = row_size;
    	col_size_ = col_size;
        //目标，全部1变为0
        //每一轮建一个checked
        //所有1的坐标都拿进去试一下
        //如果有1变成0，那就入队
        vector<vector<bool>>checked(row_size_, vector<bool>(col_size_, false));

        int step = 0;

        deque<vector<int>>bfs_queue;
        for (int r=0; r<row_size_; r++)
        {
	        for (int c=0; c<col_size_;c++)
	        {
                bool first_available = grid[r][c] == 1;
                bool first_visited = checked[r][c];

                //未访问，满足要求，入队
                if (!first_visited && first_available)
                {
                    bfs_queue.push_back({ r,c });
	                //标为已访问
                    checked[r][c] = true;
                    step += 1;
                    bfs(grid, checked, bfs_queue);
                }
	        }
        }

        cout << step;
        //上、下、左、右 左上、左下、右上、右下
        //Solution02
    }
private:
    int row_size_ = 0, col_size_ = 0;
    vector<vector<int>>DirectionGrid = {
        {-1,0},{1,0},{0,-1},{0,1},
		{-1,-1},{1,-1},{-1,1},{1,1}
    };
};


/*
歌手准备从 A 城去 B 城参加演出 

必须在 T 天内赶到。 
2. 歌手途径 N 座城市。 
3. 歌手不能往回走。 
4. 每两座城市之间需要的天数都可以提前获知。 
5. 歌手在每座城市都可以在路边卖唱赚钱
经过调研，歌手提前获知了每座城市卖唱的收入预期
如果在一座城市第一天卖唱可以赚 M，后续每天的收入会减少 D (第二天赚的钱是 M-D，第三天是 M-2D…)
如果收入减到 0 就不会再少
6. 歌手到达后的第二天才能开始卖唱
如果今天卖过唱，第二天才能出发
问贪心的歌手最多可以赚多少钱?

输入
第一行两个数字 T 和 N，中间用空格隔开，T 代表总天数；
N 代表路上经过 N 座城市;
0 < T < 1000，0 < N < 100
第二行 N+1 个数字，中间用空格隔开，代表每两座城市之间耗费的时间，其总和<=T
接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的收入预期
0 < M < 1000，0 < D < 100

输出
一个数字。代表歌手最多可以赚多少钱。以回车结束

输入
10 2
1 1 2
120 20
90 10
输出
540
 */
class Solution03
{
public:
    struct Node
    {
        int val, diff;
        Node() = default;
        Node(int val, int diff) :val(val), diff(diff) {};
        bool operator<(const Node&other) const
        {
            return val < other.val;
        }
    };
    Solution03(int total, vector<int>&cost_v, vector<vector<int>>&choose_v)
    {
        int cost_day = 0;
        for (auto&day:cost_v)
        {
            cost_day += day;
        }
        int remain_day = total - cost_day;

        priority_queue<Node>p_queue;
        for (auto&item:choose_v)
        {
            //val diff
            Node node(item[0], item[1]);
            p_queue.push(node);
        }

        int result = 0;
        while (!p_queue.empty()&&remain_day>0)
        {
            Node top_node = p_queue.top();
            p_queue.pop();
            result += top_node.val;
            remain_day -= 1;
            top_node.val -= top_node.diff;

            if (top_node.val>0)
            {
                p_queue.push(top_node);
            }

            //while
        }
        cout << result;
	    //Solution03
    }
};

int main()
{
	{
/*
10 2
1 1 2
120 20
90 10
*/
        int total, v_size;
        cin >> total >> v_size;

        vector<int>cost_v(v_size+1);
        for (int i=0; i<v_size+1; i++)
        {
            cin >> cost_v[i];
        }

        vector<vector<int>>choose_v(v_size, vector<int>(2));
        for (int i=0; i<v_size; i++)
        {
            cin >> choose_v[i][0] >> choose_v[i][1];
        }

        Solution03 solu(total, cost_v, choose_v);

        return 0;
	}
	{
/*
3 3
1 0 1
0 1 0
1 0 1
*/
        int row_size, col_size;
        cin >> row_size >> col_size;

        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size;c++)
	        {
                cin >> grid[r][c];
	        }
        }

        Solution02 solu(grid, row_size, col_size);

        return 0;
	}
/*
4,5
10,6,9,7,6
9,10,6,7,5
8,10,6,5,10
9,10,8,4,9
*/
    string size_input;
    getline(cin, size_input);
    stringstream input_ss1(size_input);
    string token;
    vector<int>size_v;
    while (getline(input_ss1,token,','))
    {
        size_v.push_back(stoi(token));
    }
    int row_size = size_v[0];
    int col_size = size_v[1];
    //1~N（3<=N<=100）M（3 <= M <= 10）
    bool is_row_size = row_size >= 3 && row_size <= 100;
    bool is_col_size = col_size >= 3 && col_size <= 100;
    if (!is_row_size || !is_col_size)
    {
        cout << -1;
        return 0;
    }
    vector<vector<int>>grid;
    for (int i=0; i<row_size; i++)
    {
        vector<int>item_v;
        string input;
        getline(cin, input);
        stringstream input_ss2(input);
        while (getline(input_ss2,token,','))
        {
            item_v.push_back(stoi(token));
        }
        grid.push_back(item_v);
    }
    Solution01 solu(grid, row_size, col_size);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
